from itertools import accumulate
from typing import *


class Solution:
    def shiftDistance(
        self, s: str, t: str, nextCost: List[int], previousCost: List[int]
    ) -> int:
        next = [[0] * 26 for _ in range(26)]
        for i in range(26):
            next[i][1] = nextCost[i]
        for j in range(2, 26):
            for i in range(26):
                next[i][j] = next[i][j - 1] + nextCost[(i + (j - 1)) % 26]
        prev = [[0] * 26 for _ in range(26)]
        for i in range(26):
            prev[i][1] = previousCost[i]
        for j in range(2, 26):
            for i in range(26):
                prev[i][j] = prev[i][j - 1] + previousCost[(i - (j - 1) + 26) % 26]
        dist = [[0] * 26 for _ in range(26)]
        for i in range(26):
            for j in range(26):
                dist[i][j] = min(next[i][(j - i + 26) % 26], prev[i][(i - j + 26) % 26])
        ans = 0
        for a, b in zip(s, t):
            ans += dist[ord(a) - ord("a")][ord(b) - ord("a")]
        return ans


a = list(range(10))
print(a)
# print(list(accumulate(a)))
print(list(accumulate(a, initial=0)))


class Solution:
    def shiftDistance(
        self, s: str, t: str, nextCost: List[int], previousCost: List[int]
    ) -> int:
        nxt_sum = list(accumulate(nextCost + nextCost, initial=0))
        pre_sum = list(accumulate(previousCost + previousCost, initial=0))

        ans = 0
        ord_a = ord("a")
        for x, y in zip(s, t):
            x = ord(x) - ord_a
            y = ord(y) - ord_a
            ans += min(
                nxt_sum[y + 26 if y < x else y] - nxt_sum[x],
                pre_sum[(x + 26 if x < y else x) + 1] - pre_sum[y + 1],
            )
        return ans
